import java.util.Random;

public class FindKthLargest_2 {
    static Random random = new Random();
    public static int findKthLargest(int[] nums, int k) {

        return quickSort(nums,k,0,nums.length-1);

    }

    public static int quickSort(int[] nums,int k,int left,int right){
        int index = random.nextInt(right-left+1)+left; //随机选择基准点
        int flag = nums[index]; //保留基准点的值
        nums[index] = nums[left];//基准点的值替换为最左边的值
        int i = left;
        int j = right;
        while (i<j){
            while (i<j&&nums[j]<=flag)
                j--;
            nums[i]=nums[j];
            while (i<j&&nums[i]>=flag)
                i++;
            nums[j]=nums[i];
        }
        nums[i] = flag;
        if (i==k-1)




            return nums[i];
        else if (i<k-1){
            return quickSort(nums,k,i+1,right);
        }else {
            return quickSort(nums,k,left,i-1);
        }
    }

    public static void main(String[] args) {
        int[] nums = {5,3,2,6,3,1};
        findKthLargest(nums,2);
    }

}
